#ifndef _MATRIX_GRAPH_H_
#define _MATRIX_GRAPH_H_

#include "Graph.h"
#include "Exception.h"
#include "DynamicArray.h"

namespace MySTL
{

template < int N, typename V, typename E >
class MatrixGraph : public Graph<V, E>
{
public:
	MatrixGraph();
	~MatrixGraph();

	V& getVertex(int n);
	const V& getVertex(int n) const;
	bool getVertex(int n, V& value) const;
	bool setVertex(int n, const V& value);
	SharedPointer< Array<int> > getAdjacent(int n) const;
	E& getEdge(int i, int j);
	const E& getEdge(int i, int j) const;
	bool getEdge(int i, int j, E& value) const;
	bool setEdge(int i, int j, const E& value);
	bool removeEdge(int i, int j);
	int VCount() const;
	int ECount() const;
	int IDegree(int n) const;
	int ODegree(int n) const;
	bool isAdjacent(int i, int j) const;

protected:
	V* m_vertex[N];
	E* m_edge[N][N];
	int m_edgeCount;
};

template < int N, typename V, typename E >
MatrixGraph<N, V, E>::MatrixGraph()
{
	for (int i = 0; i < N; ++i)
	{
		m_vertex[i] = NULL;

		for (int j = 0; j < N; ++j)
		{
			m_edge[i][j] = NULL;
		}
	}

	m_edgeCount = 0;
}

template < int N, typename V, typename E >
MatrixGraph<N, V, E>::~MatrixGraph()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			E* toDel = m_edge[i][j];
			if (NULL != toDel)
			{
				--m_edgeCount;
				m_edge[i][j] = NULL;

				delete toDel;
			}
		}

		delete m_vertex[i];
	}
}

template < int N, typename V, typename E >
V& MatrixGraph<N, V, E>::getVertex(int n)
{
	if (n >= 0 && n < VCount())
	{
		if (NULL != m_vertex[n])
		{
			return *(m_vertex[n]);
		}
		else
		{
			THROW_EXCEPTION(InvalidOperationException, "No such vertex in V& MatrixGraph<N, V, E>::getVertex(int n)");
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in V& MatrixGraph<N, V, E>::getVertex(int n)");
	}
}

template < int N, typename V, typename E >
const V& MatrixGraph<N, V, E>::getVertex(int n) const
{
	return const_cast<MatrixGraph<N, V, E>*>(this)->getVertex(n);
}

template < int N, typename V, typename E >
bool MatrixGraph<N, V, E>::getVertex(int n, V& value) const
{
	bool ret = (n >= 0 && n < VCount() && (NULL != m_vertex[n]));

	if (ret)
	{
		value = *(m_vertex[n]);
	}

	return ret;
}

template < int N, typename V, typename E >
bool MatrixGraph<N, V, E>::setVertex(int n, const V& value)
{
	bool ret = (n >= 0 && n < VCount());

	if (ret)
	{
		V* vertex = m_vertex[n];

		if (NULL == vertex)
		{
			vertex = new V();
		}

		if (NULL != vertex)
		{
			*vertex = value;
			m_vertex[n] = vertex;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create vertex in bool MatrixGraph<N, V, E>::setVertex(int n, const V& value)");
		}
	}

	return ret;
}

template < int N, typename V, typename E >
SharedPointer< Array<int> > MatrixGraph<N, V, E>::getAdjacent(int n) const
{
	Array<int>* ret = NULL;

	if (n >= 0 && n < VCount())
	{
		int count = 0;

		for (int i = 0; i < N; ++i)
		{
			if (NULL != m_edge[n][i])
			{
				++count;
			}
		}

		if (count > 0)
		{
			ret = new DynamicArray<int>(count);

			if (NULL != ret)
			{
				count = 0;
				for (int i = 0; i < N; ++i)
				{
					if (NULL != m_edge[n][i])
					{
						(*ret)[count++] = i;
					}
				}
			}
			else
			{
				THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory in SharedPointer< Array<int> > MatrixGraph<N, V, E>::getAdjacent(int n) const");
			}
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in SharedPointer< Array<int> > MatrixGraph<N, V, E>::getAdjacent(int n) const");
	}

	return ret;
}

template < int N, typename V, typename E >
E& MatrixGraph<N, V, E>::getEdge(int i, int j)
{
	if ((i >= 0 && i < VCount()) && (j >= 0 && j < VCount()))
	{
		if (NULL != m_edge[i][j])
		{
			return *(m_edge[i][j]);
		}
		else
		{
			THROW_EXCEPTION(InvalidOperationException, "No such edge in E& MatrixGraph<N, V, E>::getEdge(int i, int j)");
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in E& MatrixGraph<N, V, E>::getEdge(int i, int j)");
	}
}

template < int N, typename V, typename E >
const E& MatrixGraph<N, V, E>::getEdge(int i, int j) const
{
	return const_cast<MatrixGraph<N, V, E>*>(this)->getEdge(i, j);
}

template < int N, typename V, typename E >
bool MatrixGraph<N, V, E>::getEdge(int i, int j, E& value) const
{
	bool ret = (i >= 0 && i < VCount()) && (j >= 0 && j < VCount()) && (NULL != m_edge[i][j]);

	if (ret)
	{
		value = *(m_edge[i][j]);
	}

	return ret;
}

template < int N, typename V, typename E >
bool MatrixGraph<N, V, E>::setEdge(int i, int j, const E& value)
{
	bool ret = (i >= 0 && i < VCount()) && (j >= 0 && j < VCount()) && (i != j);

	if (ret)
	{
		E* edge = m_edge[i][j];

		if (NULL == edge)
		{
			edge = new E();
		}

		if (NULL != edge)
		{
			*edge = value;

			if (NULL == m_edge[i][j])
				++m_edgeCount;

			m_edge[i][j] = edge;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create edge in bool MatrixGraph<N, V, E>::setEdge(int i, int j, const E& value)");
		}
	}

	return ret;
}

template < int N, typename V, typename E >
bool MatrixGraph<N, V, E>::removeEdge(int i, int j)
{
	bool ret = (i >= 0 && i < VCount()) && (j >= 0 && j < VCount()) && (NULL != m_edge[i][j]);

	if (ret)
	{
		E* toDel = m_edge[i][j];

		m_edge[i][j] = NULL;
		--m_edgeCount;
		
		delete toDel;
	}

	return ret;
}

template < int N, typename V, typename E >
int MatrixGraph<N, V, E>::VCount() const
{
	return N;
}

template < int N, typename V, typename E >
int MatrixGraph<N, V, E>::ECount() const
{
	return m_edgeCount;
}

template < int N, typename V, typename E >
int MatrixGraph<N, V, E>::IDegree(int n) const
{
	int ret = 0;

	if (n >= 0 && n < VCount())
	{
		for (int i = 0; i < N; ++i)
		{
			if (NULL != m_edge[i][n])
			{
				++ret;
			}
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in int MatrixGraph<N, V, E>::IDegree(int n) const");
	}

	return ret;
}

template < int N, typename V, typename E >
int MatrixGraph<N, V, E>::ODegree(int n) const
{
	int ret = 0;

	if (n >= 0 && n < VCount())
	{
		for (int i = 0; i < N; ++i)
		{
			if (NULL != m_edge[n][i])
			{
				++ret;
			}
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in int MatrixGraph<N, V, E>::ODegree(int n) const");
	}

	return ret;
}

template < int N, typename V, typename E >
bool MatrixGraph<N, V, E>::isAdjacent(int i, int j) const
{
	bool ret = false;

	if ((i >= 0 && i < VCount()) && (j >= 0 && j < VCount()))
	{
		ret = (m_edge[i][j] != NULL);
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in bool MatrixGraph<N, V, E>::isAdjacent(int i, int j) const");
	}

	return ret;
}

}

#endif